package leetcode.editor.cn;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;

/**
 * @author: yangwk
 * @date: 2023/10/18
 * @description:
 **/
public class P480 {
    public static void main(String[] args) {
        Arrays.stream(medianSlidingWindow(new int[]{1, 4, 2, 3}, 4)).forEach(System.out::println);
    }

    public static double[] medianSlidingWindow(int[] nums, int k) {
        int left = 0, right = 0;
        int medIndex = 0;
        double[] medArr = new double[nums.length - k + 1];
        List<Integer> window = new ArrayList<>();
        while (right < nums.length) {
            insert(window, nums[right]);
            if (right - left == k - 1) {
                if (k % 2 == 0) {
                    int first = k / 2;
                    int second = k / 2 - 1;
                    medArr[medIndex++] = window.get(first) / 2.0 + window.get(second) / 2.0;
                } else {
                    int first = k / 2;
                    medArr[medIndex++] = window.get(first);
                }
                int search = search(window, nums[left]);
                window.remove(search);
                left++;
            }
            right++;
        }
        return medArr;
    }

    //最简单的二分查找
    private static int search(List<Integer> window, int target) {
        int start = 0;
        int end = window.size() - 1;
        while (start <= end) {
            int mid = start + (end - start) / 2;
            if (window.get(mid) > target) {
                end = mid - 1;
            } else if (window.get(mid) < target) {
                start = mid + 1;
            } else {
                return mid;
            }
        }
        return -1;
    }

    public static void insert(List<Integer> arr, int x) {
        arr.add(x);
        int index = arr.size() - 1;
        while (index > 0 && arr.get(index - 1) > arr.get(index)) {
            Integer max = arr.get(index - 1);
            Integer min = arr.get(index);
            arr.set(index - 1, min);
            arr.set(index, max);
            index--;

        }
    }


}
